public final class Hconstructiva extends Ejercicio
{ 
	public int[] Vo1, Vo2;
	public int cruces;
	
	protected Resultado DGIB
	(
			int n1, int v1[], int n2, int v2[], int m, Eje v1v2[],
			int np1, int vp1[], int np2, int vp2[], int mp, Eje vp1vp2[]
	){
		Resultado res = new Resultado();
		
		/*PRIMERA HEURISTICA CONSTRUCTIVA: 
		 Esta heuristica va eligiendo el mejor lugar para cada nodo
		 (para que genere la minima cantidad de cruces)...partiendo del
		 bipartito incremental*/
		
		int i; 
		int M = m + mp;
		int N1 = n1 + np1;
		int N2 = n2 + np2;
		
		Nodo[] IV1 = new Nodo[N1], IV2 = new Nodo[N2];
		Eje[] IV1V2 = new Eje[M];
		
		//4 declaraciones
		//3 declaraciones-asignaciones
		//3 operaciones basicas
		addPasos(10);
		
		for( i = 0; i < n1; i++ )
			IV1[i] = new Nodo(v1[i],false);
		
		for( i = 0; i < np1; i++ )
			IV1[n1+i] = new Nodo(vp1[i],true);
		
		for( i = 0; i < n2; i++ )
			IV2[i] = new Nodo(v2[i],false);
		
		for( i = 0; i < np2; i++ )
			IV2[n2+i] = new Nodo(vp2[i],true);
		
		for( i = 0; i < m; i++ )
			IV1V2[i] = v1v2[i];
		
		for( i = 0; i < mp; i++ )
			IV1V2[m+i] = vp1vp2[i];
		
		//n1 comparaciones
		//n1 operaciones basicas
		//n1 declaraciones-asignaciones
		//np1 comparaciones
		//np1*2 operaciones basicas
		//np1 declaraciones-asignaciones
		//n2 comparaciones
		//n2 operaciones basicas
		//n2 declaraciones-asignaciones
		//np2 comparaciones
		//np2*2 operaciones basicas
		//np2 declaraciones-asignaciones
		//m comparaciones
		//m operaciones basicas
		//m declaraciones-asignaciones
		//mp comparaciones
		//mp*2 operaciones basicas
		//mp comparaciones
		//mp declaraciones-asignaciones
		addPasos( n1*3+np1*4+n2*3+np2*4+m*3+mp*4 );
		
		//cruce maximo de ejes
		this.cruces = M*(M-1);
		//solucion optima
		this.Vo1 = new int[N1];
		this.Vo2 = new int[N2];
		
		constructiva
		(
			IV1, N1,
			IV2, N2,
			IV1V2, M
		);
		
		//1 declaracion
		//2 operaciones basicas
		//2 declaraciones-asignaciones
		//1 llamada a funcion
		addPasos(6);
		
		for( int l = 0; l < N1; l++ )
			this.Vo1[l] = IV1[l].valor;
		
		for(int l = 0; l < N2; l++ )
			this.Vo2[l] = IV2[l].valor;
		
		cruces = cantidadCruces(Vo1,N1,Vo2,N2,IV1V2,M);
		
		res.kid = cruces;
		res.n_iv1 = N1;
		res.iv1 = Vo1; 
		res.n_iv2 = N2;
		res.iv2 = Vo2;
		
		//N1 veces:
			//1 comparacion
			//1 operacion basica
			//1 asignacion
		//N2 veces:
			//1 comparacion
			//1 operacion basica
			//1 asignacion
		//2 comparaciones
		//8 asignaciones
		//1 llamada a funcion
		addPasos((N1+N2)*3+11);
		
		return res;
	}

	public void constructiva
	(
		Nodo[] IV1, int N1,
		Nodo[] IV2, int N2,
		Eje[] IV1V2, int M
	){		
		permutacionOptima(IV1, N1, IV2, N2, IV1V2, M, false);
		permutacionOptima(IV2, N2, IV1, N1, IV1V2, M, true);
		
		//2 llamadas a funciones
		addPasos(2);
	}
	
	private void permutacionOptima(
			Nodo Vmovil[], int Nmovil,
			Nodo Vfijo[], int Nfijo,
			Eje V1V2[], int M,
			boolean invertir
	){
		int i = 0, k, l, n, c=0, best_i = 0, best_c = M*(M-1);
		Nodo v;
		
		//4 declaraciones-asignaciones
		//4 declaraciones
		//2 operaciones basicas
		addPasos(10);
		
		while( i < Nmovil )
		{
			if(Vmovil[i].incremental)
			{
				v = Vmovil[i];
				v.incremental = false;
				k = 0;
				n = i;
				
				best_c = M*(M-1);
				
				//5 asignaciones
				//2 operaciones basicas
				addPasos(7);
				
				while( k < Nmovil )
				{	
					if(k == 0)
					{
						for( l = n; l > k; l-- )
						{
							swap(Vmovil, l,l-1);
							
							//1 comparacion
							//2 operaciones basicas
							//1 llamada a funcion
							addPasos(4);
						}
						
						//antes del ciclo
							//1 asignacion
						//despues del ciclo
							//1 comparacion
						addPasos(2);
					}
					else
					{
						swap(Vmovil,n,k);
						
						//1 llamada a funcion
						addPaso();
					}
					
					//1 comparacion
					addPaso();

					for(int j = 0; j < M; j++)
					{
						if( invertir )
						{
							if(V1V2[j].destino == v.valor)
							{
								c = CrucesDelEje(Vfijo, Nfijo, Vmovil, Nmovil, V1V2, M,V1V2[j]);
							}
						}
						else
						{
							if(V1V2[j].origen == v.valor)
							{
								c = CrucesDelEje(Vmovil, Nmovil, Vfijo, Nfijo, V1V2, M,V1V2[j]);
							}
						}
						
						//2 comparaciones
						//2 operaciones basicas
						//1 asignacion
						//1 llamada a funcion
						addPasos(6);
					}
					
					//antes del ciclo
						//1 asignacion
					//despues del ciclo
						//1 comparacion
					addPasos(2);
					
					if(c < best_c)
					{
						best_i = k;
						best_c = c;
						
						//2 asignaciones
						addPasos(2);
					}

					n = k;
					k++;
					
					if(best_i <= i)
					{
						i++;
						
						//1 operacion basica
						addPaso();
					}
					
					//3 comparaciones
					//1 asignacion
					//1 operacion basica
					addPasos(5);
				}
				
				//cuando sale del ciclo:
					//1 comparacion
				addPaso();
				
				for( l = n; l > best_i; l-- )
				{
					swap(Vmovil, l,l-1);
					
					//1 comparacion
					//2 operaciones basicas
					//1 llamada a funcion
					addPasos(4);
				}
				
				//antes del ciclo
					//1 asignacion
				//despues del ciclo
					//1 comparacion
				addPasos(2);
			}
			else
			{
				i++;
				
				//1 operacion basica
				addPaso();
			}
			
			//2 comparaciones
			addPasos(2);
		}
		
		//cuando sale del ciclo
			//1 comparacion
		addPaso();
	}
}